The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
An access control list (ACL) specifies what network traffic should be allowed and what traffic should be blocked. An ACL is a list of data structures. Each data structure includes multiple attributes (e.g., objects), such as source address, destination address, and action. An example ACL is shown below:                permit http 171.78.78.0/24 host 132.130.25.66        permit http 171.78.79.0/24 host 132.130.25.66        permit http 169.21.42.0/24 host 132.130.25.66        permit http 153.60.68.0/24 host 132.130.25.66        permit http 171.78.78.0/24 host 132.130.25.121        permit http 171.78.79.0/24 host 132.130.25.121        permit http 169.21.42.0/24 host 132.130.25.121        permit http 153.60.68.0/24 host 132.130.25.121An ACL may be used to control operation of network infrastructure devices, such as firewalls. The above ACL allows four networks to access two web servers (host 132.130.25.66 and host 132.130.25.121).        
Using an object grouping technique can reduce a size of an ACL. The object grouping technique allows multiple source addresses and multiple destination addresses to be placed in a single ACL entry. The technique compresses the size of the ACL by removing redundant information. Using the technique usually reduces the size of an ungrouped ACL to a fraction of that ACL's original size. A significant performance improvement results. Storing the ACL requires less memory. Filtering packets requires less time. The ACL can be transmitted in less time.
The object grouping technique can be used with other lists of data structures. For example, attributes of data structures in a security policy list may also be grouped. Each data structure (i.e., policy) in a security policy list includes, as attributes of that data structure, a source object, a destination object, a service, and an action. Each attribute of a data structure corresponds to a dimension of the security policy list. For each dimension of the security policy list, each data structure in the security policy list includes an attribute corresponding to that dimension. For example, one dimension may correspond to a source object of each data structure, one dimension may correspond to a destination object of each data structure, and one dimension may correspond to a service of each data structure.
If two data structures include a common action (e.g., permit) and common attributes corresponding to two of the three dimensions, then those two data structures can be combined into one combined data structure. The combined data structure includes the same common action and common attributes corresponding to those two dimensions. In its remaining attribute corresponding to the third dimension, the combined data structure includes a set that includes the uncommon third-dimension attributes of both of the data structures being combined. That set is called an object group. For example, two policies                permit telnet from A to B        permit http from A to Bcan be combined into one policy        permit {telnet, http} from A to Bwhere {telnet, http} is a new service object group. Objects are optimally grouped if there are no data structures in the list that can be further combined.        
However, some existing firewall software does not support object groups. ACLs and security policy lists formed for use with such software do not include object groups. When upgrading to firewall software that supports object groups, a human user is left with the frequently onerous task of manually grouping objects in an list that does not include object groups. Given that a usual list may include several thousand data structures, such manual grouping can be time-consuming and provides abundant opportunities for a human user to introduce errors. A human user may also have difficulty determining an optimal grouping for a list; that is, a human user may have difficulty grouping objects in the data structures of a list so that all redundant information is removed from those data structures.
One possible approach to object grouping is a pair-wise comparison approach. Using the pair-wise comparison approach, each policy in a security policy list is compared with every other policy in that list, and policies are combined if those policies have (1) the same action, and (2) two identical attributes in the same dimensions.
The pair-wise comparison approach has a time complexity of O(n2). For example, using the pair-wise comparison approach, a computer combined 25033 original policies into 222 combined policies in 3 minutes and 51 seconds. For a computer, that is a relatively long time.
Based on the foregoing, there is a clear need for a way of automatically and optimally removing redundant information from a list of data structures using an approach that has a time complexity of less than O(n2).